## Жадины

Жадный алгоритм (англ. `Greedy algorithm`) — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Итак, жадный алгоритм — это алгоритм, который на каждом шагу делает локально наилучший выбор в надежде, что итоговое решение будет оптимальным.

К примеру, алгоритм `Дейкстры` нахождения кратчайшего пути в графе вполне себе жадный, потому что мы на каждом шагу ищем вершину с наименьшим весом, в которой мы еще не бывали, после чего обновляем значения других вершин. 

При этом можно доказать, что кратчайшие пути, найденные в вершинах, являются оптимальными.

К слову, алгоритм `Флойда`, который тоже ищет кратчайшие пути в графе (правда, между всеми вершинами), не является примером жадного алгоритма. 

Флойд демонстрирует другой метод — метод динамического программирования.


### Пример 1

* Есть N кубических коробок.
* Самой интересной считается упаковка подарка по принципу матрёшки  — подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д. 
* Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки.

Необходимо:

* Определить наибольшее количество коробок, которое можно использовать для упаковки одного подарка
* Максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок.

P.S. Размер подарка позволяет поместить его в самую маленькую коробку.

Пример входных данных:

```
43
40
32
40
30
```

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон коробок, подходящих для упаковки «матрёшкой», составляет 3 единицы.

При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон:

* 30, 40 и 43 
* 32, 40 и 43 

* т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32 .

Алгоритм:

* Сначала считаем в список `boxes` данные из файла. 

* После этого отсортируем список в порядке убывания.

* В список `res` сначала поместим самую большую коробку.

* Далее пройдём по оставшимся коробкам и будем добавлять в список `res` очередную коробку, если длина её стороны будет как минимум на `3` единицы меньше последнего элемента списка `res`.

### Задача 1. Отработать алгоритм на файле

[Коробки.txt](boxes.txt)

> Ответ:  2767 51

## Пример 2.

* На складе есть кубические контейнеры различного размера.
* Чтобы сократить занимаемое при хранении место, контейнеры вкладывают друг в друга.
* Один контейнер можно вложить в другой, если размер стороны внешнего контейнера превышает размер стороны внутреннего на 5 и более условных единиц.
* Группу вложенных друг в друга контейнеров называют блоком.
* Количество контейнеров в блоке может быть любым.
* Каждый блок, независимо от количества и размера входящих в него контейнеров, а также каждый одиночный контейнер, не входящий в блоки, занимает при хранении одну складскую ячейку.

> Зная количество контейнеров и их размеры, определите минимальное количество ячеек для хранения всех контейнеров и максимально возможное количество контейнеров в одном блоке.

Пример входных данных:

```
43
40
32
40
30
```

### Задача 2. Отработать алгоритм на файле

[контейнеры.txt](boxes.txt)

> Ответ:  17 и 1767
### Пример 3. Задача на заявки в конференц-зале

Есть сведения о заявках в следующем виде

```
10 150
100 110
131 170
131 180
120 130
```

* В каждой заявке указаны время начала и время окончания мероприятия (в минутах от начала суток). 
 
* Если время начала одного мероприятия меньше времени окончания другого, то провести можно только одно из них. 

* Если время окончания одного мероприятия совпадает с временем начала другого, то провести можно оба. 

* Определите максимальное количество мероприятий, которое можно провести в конференц-зале и самое позднее время окончания последнего мероприятия.

Нужно определить:
* максимальное  — количество мероприятий, которое можно провести в конференц-зале 
* самое позднее время окончания последнего мероприятия (в минутах от начала суток).

Ответ:

При таких исходных данных можно провести максимум три мероприятия, например, по заявкам `2, 3 и 5`. 

Конференц-зал освободится самое позднее на 180-й минуте, если состоятся мероприятия по заявкам `2, 4, 5`. 


### Задача 3. Отработать алгоритм на файле
[время_для_заявок.txt](time_present.txt)

> ответ: 16  1345

### Задача 4.

Написать программу для раскладки N деталей в K контейнеров, каждый из которых рассчитан на свой определённый объём. 

```python
s = '''
4 # это N
3 # это K
10
15
35
20
5
10
45
'''
```

* Следующие K строк содержат по одному целому числу  — объём каждого контейнера.

* Все детали кладут по очереди. 

* Каждую следующую деталь стараются положить в контейнер с наименьшим возможным номером. 

> Ответ: 45, 3

(объём всех отложенных деталей и их количество)

### Отработать алгоритм на файле

[контейнеры.txt](containers.txt)

> ответ: 5147132, 18746